package bintree.leetcode;

/**
 * @Author: yuisama
 * @Date: 2022/9/28 14:08
 * @Description:填充二叉树每个节点的下一个右侧指针节点
 */
public class Num116_Connect {
//    // yuisama遍历法^^
//    public Node connect(Node root) {
//        traverse(root);
//        return root;
//    }
//    public void traverse(Node root) {
//        // base case
//        if (root == null || (root.left == null && root.right == null)) {
//            return;
//        }
//        if (root.next != null) {
//            // 处理右孩子的连接
//            root.right.next = root.next.left;
//        }
//        root.left.next = root.right;
//        // 继续处理子树
//        traverse(root.left);
//        traverse(root.right);
//    }
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        traverse(root.left,root.right);
        return root;
    }
    // 三叉树遍历框架
    // node1和node2是拥有相同父节点的两个兄弟节点
    public void traverse(Node node1,Node node2) {
        // base case
        if (node1 == null || node2 == null) {
            return;
        }
        // 先连接两个树根
        node1.next = node2;
        // 前序
        traverse(node1.left,node1.right);
        traverse(node2.left,node2.right);
        // node1的右子树和node2的左子树的拼接
        traverse(node1.right,node2.left);
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
